package gold.digger;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC295 {
    public long startExecuteTime = System.currentTimeMillis();


    public class AverageTreeNode {
        public AverageTreeNode left;
        public AverageTreeNode right;
        public int count;
        public int val;

        public AverageTreeNode(int val, AverageTreeNode left, AverageTreeNode right, int count) {
            this.left = left;
            this.right = right;
            this.count = count;
            this.val = val;
        }
    }


    class MedianFinder {
        public AverageTreeNode root;

        /**
         * initialize your data structure here.
         */
        public MedianFinder() {

        }

        public void addNum(int num) {
            this.root = addNumByRecur(this.root, num);
        }

        public AverageTreeNode addNumByRecur(AverageTreeNode root, int num) {
            if (root == null) {
                return new AverageTreeNode(num, null, null, 1);
            }

            root.count += 1;
            if (root.val > num) {
                root.left = addNumByRecur(root.left, num);
            } else {
                root.right = addNumByRecur(root.right, num);
            }

            return root;
        }


        public int findK(AverageTreeNode root, int k) {
            if (root == null || root.count < k || k < 0) {
                return -1;
            }

            int leftCount = root.left == null ? 0 : root.left.count;

            if (leftCount == k) {
                return root.val;
            }

            if (leftCount < k) {
                return findK(root.right, k - leftCount - 1);
            } else {
                return findK(root.left, k);
            }
        }

        public double findMedian() {
            if (root.count % 2 == 0) {
                return (((double) findK(root, root.count / 2)) + findK(root, (root.count - 1) / 2)) / 2;
            } else {
                return findK(root, root.count / 2);
            }
        }
    }

    /**
     * Your LessFinder object will be instantiated and called as such:
     * LessFinder obj = new LessFinder();
     * obj.addNum(num);
     * double param_2 = obj.findMedian();
     */


    public boolean run() {
        MedianFinder me = new MedianFinder();
        me.addNum(5);
        me.addNum(3);
        me.addNum(8);
        me.addNum(2);
        me.addNum(4);
        me.addNum(7);
        me.addNum(10);
        for (int i = 0; i < 7; i++) {
            System.out.println(me.findK(me.root, i));
        }
        return true;
    }


    public static void main(String[] args) throws Exception {
        LC295 an = new LC295();
        an.run();

        System.out.println("\nanswer total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
